package cn.zyl.demo.java.sort;

import java.util.Arrays;

/**
 * RadixSort 类说明: 基数排序 vs 计数排序 vs 桶排序
 * <p>基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。</p>
 * <p>由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数</p>
 * @author wsz
 * @version v1.0
 * @date 2020-08-13
 */
public class RadixSort extends AbstractArraySortSimple{
    /**
     * 排序接口
     * <p>利用了桶的概念,根据键值的每位数字来分配桶</p>
     * @param sourceArray 待排序数组
     * @param order       排序方式，(默认)升序 true；降序 false
     * @return 排序后的数组
     * @throws Exception 异常信息
     */
    @Override
    public Integer[] sort(Integer[] sourceArray, Boolean order) throws Exception {
        int len = sourceArray.length;
        Integer[] arr = copyArray(sourceArray,len);
        start();
        //最高位数
        int maxDigit = getMaxDigit(arr);
        // (123%10)/1 3；(123%100)/10 2
        int mod = 10,dev = 1,bucket,pos;
        //桶
        Integer[][] counter;
        for (int i = N_0; i < maxDigit; i++,dev *= N_10,mod *= N_10) {
            addOne();
            // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
            counter = new Integer[N_10 * N_2][0];
            for (int j = N_0; j < len; j++) {
                bucket = ((arr[j] % mod) / dev) + N_10;
                counter[bucket] = append(counter[bucket],arr[j]);
            }
            if(!order && i >= maxDigit-1){
                //降序，在最后一圈的时候进行特殊处理
                pos =  len-1;
                for (Integer[] buckets : counter){ for(Integer val : buckets){ arr[pos--] = val; } }
            }else{
                pos = N_0;
                for (Integer[] buckets : counter){ for(Integer val : buckets){ arr[pos++] = val; } }
            }
        }
        end();
        return arr;
    }
    private int getMaxDigit(Integer[] arr){
        int max = getMaxVal(arr);
        return getNumLen(max);
    }
    /** 最大数字*/
    private int getMaxVal(Integer[] arr){
        int max = arr[0];
        for(int val:arr){
            if(max < val){ max =val;}
        }
        return max;
    }
    /** 数字的长度*/
    private int getNumLen(int num){
        if(num == 0){return 1;}
        int len = 0;
        for (int i = num; i != 0; i/=N_10) {
            len ++;
        }
        return len;
    }
    /**
     * 自动扩容，并保存数据
     * @param arr 数组
     * @param val 值
     */
    private Integer[] append(Integer[] arr,int val){
        arr = Arrays.copyOf(arr, arr.length+N_1);
        arr[arr.length - N_1] = val;
        return  arr;
    }
    public static void main(String[] args) {
        int len =35,max=10000;
        //待排序数组初始化
        Integer[] arr = randomArray(len,max);
        AbstractArraySortSimple sort = new RadixSort();
        try {
            System.out.println("升序操作");
            printArray(sort.sort(arr, true));
            System.out.println("降序降序");
            printArray(sort.sort(arr, false));
        }catch (Exception e){
            e.printStackTrace();
        }
    }
}
